The invention relates to the interleaving of data signals.
In modern telecommunications systems, it is typical for a digital signal to be transmitted in an interleaved form to protect it against errors that might appear in the received version of the signal. Commonly, a digital signal is structured as a series of modulation symbols arranged in a series of blocks, with interleaving being applied to each of the blocks separately. In this context, interleaving amounts to a reordering of the symbols within a block, in accordance with a predetermined algorithm. The interleaving can be undone or reversed through “deinterleaving” conducted at the receiver that acquires the transmitted signal.
Interleaving and deinterleaving are used within turbo decoders. FIG. 1 illustrates a field programmable gate array (FPGA) 10 implementing a turbo decoder 12 compliant with the 3GPP (Third Generation Partnership Project) UMTS (Universal Mobile Telephone System) standards. The turbo decoder 12 comprises two constituent decoders 14 and 16, two memories 18 and 20, an interleaver 22 and a deinterleaver 24.
In operation, the turbo decoder 12 will perform a number of iterations of a decoding cycle upon a block of (estimated) modulation symbols arriving in a received transmission. A block of modulation symbols that is presently being decoded shall be referred to henceforth as the “block being decoded” or the BBD. In an iteration of the decoding cycle, two sequences of operations are performed in parallel.
In the first sequence, a set of extrinsic information for the interleaved version of the BBD is iterated. Henceforth, the set of extrinsic information for the interleaved version of the BBD shall be called the “interleaved extrinsic information block” or the IEIB. In the second sequence, a set of extrinsic information for the deinterleaved version of the BBD is iterated. Henceforth, the set of extrinsic information for the deinterleaved version of the BBD shall be called the “deinterleaved extrinsic information block” or the DEIB.
In the first sequence, an iteration of the IEIB is taken from memory 20 and is used by constituent decoder 16 in conjunction with an interleaved version of the BBD to produce a new iteration of the IEIB. The constituent decoder 16 uses, for example, a max log MAP (maximum a posteriori) algorithm to'produce the new iteration of the IEIB. The new iteration of the IEIB is then deinterleaved by deinterleaver 24 and stored into memory 18 as a new iteration of the DEIB.
In the second sequence, an iteration of the DEIB is taken from memory 18 and is used by constituent decoder 14 in conjunction with an deinterleaved version of the BBD to produce a new iteration of the DEIB. The constituent decoder 14 uses, for example, a max log MAP algorithm to produce the new iteration of the DEIB. The new iteration of the DEIB is then interleaved by interleaver 22 and stored into memory 20 as a new iteration of the IEIB.
The reordering process performed by the interleaver 22 is the reverse of the reordering process that is performed by the deinterleaver 24. FIG. 2 illustrates the reordering process that is performed by the interleaver 22. FIG. 2 illustrates a block 26 that is an iteration of the DEIB that is to be interleaved using interleaver 22 and the block 28 that results from this interleaving operation and which is an iteration of the IEIB. The position of the first data item in block 26 is indicated 30 and the position of the first data item in the second half of that block is indicated 32. The division between the halves of block 26 is shown by a dashed line. Assume now that the interleaving algorithm practised by interleaver 22 moves the content of position 30 to position 36 and that it moves the content of position 32 to position 34. These write operations are indicated 33 and 35, respectively.
In order to increase the data throughput of the turbo decoding process, faster hardware could be used or parallel processing could be introduced to the hardware that performs the two sequences of operations within the decoding cycle. Assume now that the latter option is taken and that constituent decoders 14 and 16 are each replaced by a pair of parallel decoders. Further, assume that, in a single iteration of the decoding cycle, each decoder in the pair replacing constituent decoder 14 iterates a separate half of the DEIB. Likewise, assume that, in a single iteration of the decoding cycle, each decoder in the pair replacing constituent decoder 16 operates on a separate half of the IEIB.
The decoders within each pair operate on their respective halves of the DEW or, as the case may be, the IEIB in order to produce new iterations of those halves. This requires the interleaver 22 to be restructured to accept two separate halves of an iteration of the DEIB and in response supply that extrinsic information reformatted as an iteration of the IEIB, but again divided into two separate halves. Likewise, it requires the deinterleaver 24 to be restructured to accept two separate halves of an iteration of the IEIB and in response supply that extrinsic information reformatted as an iteration of the DEIB but again divided into two separate halves. FIG. 3 illustrates the reordering process that will be performed by the restructured interleaver.
FIG. 3 illustrates the same block 26 that was shown in FIG. 2, and the same two locations 30 and 32 within that block. It will be apparent that locations 30 and 32 now lie in separate halves of an iteration of the DEIB. The block to which this extrinsic information is sent is now split into two halves, 38 and 40. Since the interleaving algorithm has not changed at the block level, the content of locations 30 and 32 are still mapped to locations 34 and 36. However, both of the locations 34 and 36 now lie in the first half 38.
Assume now that the restructured interleaver attempts to create the halves 38 and 40 simultaneously by processing the two halves of block 26 in parallel. Under such circumstances, the restructured interleaver will attempt to write the contents of locations 30 and 32 into half 38 simultaneously. Assume now that the halves of block 26 and the two halves 38 and 40 occupy separate memory blocks within the FPGA 10 and that, as is usual, data can only be written serially to these memory blocks. Given that half 38 is within a single memory block it is therefore not possible to perform the write operations 33 and 35 simultaneously with the result that the restructured interleaver cannot operate.